package day1009;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
mark
/**
 * Description:
 * 最近卡斯丁狗爱上了‘我的世界’ 这个游戏，一直在里面挖矿，种地，养牛，造铁轨等，还经常邀请double x,
 * ayer等很多基友去他的世界玩。这一天。他们发现了一大片树林，然后忍不住的去开始砍，但是砍着砍着天都黑了，
 * 正如你所知，黑夜是那么的口怕，关键是他们出来砍树为了节省背包，没有带床，只好自己回家睡觉。卡斯丁狗 
 * 想知道有几个人不比他晚到家。他们砍树的区域是n*m的矩形，‘S'表示卡斯丁狗的位置，’E‘表示家的位置，’.‘
 * 表示是可以走的平地，'T'表示是树，不能走，数字x表示的是那个位置有x个卡斯丁狗的基友。
 * (当然数字位置也是可以走的，某点可以到达与他有边相连的位置)
 * Sample Input:
 * 5 7
 * 000E0T3
 * T0TT0T0
 * 010T0T0
 * 2T0T0T0
 * 0T0S000
 * 1 4
 * SE23
 * @author chenxiaokang
 *
 */
public class Ques1676 {
	
	char[][] map;
	Map<String,Integer> vis;
	LinkedList<Integer> queueX;
	LinkedList<Integer> queueY;
	Map<String,Integer> len;
	int index;
	int x;
	int y;

	public void go(){
//		map = new char[1010][1010];
		map = new char[][]{{'0','0','0','E','0','T','3'},{'T','0','T','T','0','T','0'},
			{'0','1','0','T','0','T','0'},{'2','T','0','T','0','T','0'},{'0','T','0','S','0','0','0'}};
		x = map.length;
		y = map[0].length;
		queueX = new LinkedList<Integer>();
		queueY = new LinkedList<Integer>();
		vis = new HashMap();
		len = new HashMap();
		index = 0;
		bfs();
	}
	
	public void bfs(){
		outter:for( int i = 0; i < x; i++ ){
			for( int j = 0; j < y; j ++ ){
				if(map[i][j] == 'E'){
					queueX.addFirst(i);
					queueY.addFirst(j);
					break outter;
				}
			}
		}
		
		vis.put(queueX.getFirst() + "," + queueY.getFirst(), index);
		
		while(!queueX.isEmpty()){
			int nowX = queueX.poll();
			int nowY = queueY.poll();
			index++;
			
//			if(map[nowX+1][nowY] == 'T' || map[nowX-1][nowY] == 'T'||map[nowX][nowY+1] == 'T'||map[nowX][nowY-1] == 'T'){
//				continue;
//			}else if(map[nowX][nowY] != 'E' && (int)map[nowX][nowY] > 0){
//				len.put(nowX + "," + nowY, index);
//			}
			
			if(nowX + 1 < x && !vis.containsKey((nowX + 1)+","+(nowY))){
				queueX.addLast(nowX + 1);
				queueY.addLast(nowY);
				vis.put((nowX + 1)+","+(nowY), index);
			}
			
			if(nowY + 1 < y && !vis.containsKey((nowX)+","+(nowY + 1))){
				queueX.addLast(nowX);
				queueY.addLast(nowY + 1);
				vis.put((nowX)+","+(nowY+1), 1);
			}
			
			if(nowX - 1 > 0 && !vis.containsKey((nowX - 1)+","+(nowY))){
				queueX.addLast(nowX - 1);
				queueY.addLast(nowY);
				vis.put((nowX - 1)+","+(nowY), 1);
			}
			
			if(nowY - 1 > 0 && !vis.containsKey((nowX)+","+(nowY - 1))){
				queueX.addLast(nowX);
				queueY.addLast(nowY - 1);
				vis.put((nowX)+","+(nowY - 1), 1);
			}
		}
		
		for(Map.Entry<String, Integer> entry : vis.entrySet()){
			String key =  entry.getKey();
			int value = entry.getValue();
//			System.out.println("x:"+Integer.parseInt(key.charAt(0)+""));
//			System.out.println("y:"+Integer.parseInt(key.charAt(2)+""));
			System.out.print(map[Integer.parseInt(key.charAt(0)+"")][Integer.parseInt(key.charAt(2)+"")]+" ");
		}
	}
	
	public static void main(String[] args) {
		new Ques1676().go();
	}
}
